package poset;

import graphs.CycleException;
import graphs.DirectedGraph;
import graphs.NoCycleGraph;
import graphs.NoMultiplicityGraph;

import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

public class SphericalPoset implements NoCycleGraph, NoMultiplicityGraph, DirectedGraph{
	
	private TreeSet<SphericalOrdering> orderings = new TreeSet<SphericalOrdering>();
	private TreeMap<SphericalItem,SphericalInternalNode> iNodes = new TreeMap<SphericalItem,SphericalInternalNode>();
	//private ArrayList<SphericalInternalNode> heads = new ArrayList<SphericalInternalNode>();
	//private ArrayList<SphericalInternalNode> tails = new ArrayList<SphericalInternalNode>();
	private TreeSet<SphericalItem> items = new TreeSet<SphericalItem>();
	
	public SphericalPoset(){}
	
	public SphericalPoset(TreeSet<SphericalOrdering> orderings) throws CycleException, ExplicitRedundancyException{
		this.orderings = orderings;
		for(SphericalOrdering ordering : orderings){
			addOrdering(ordering);
		}
	}

	public TreeSet<SphericalOrdering> getOrderings() {
		return orderings;
	}
	
	public void addOrdering(SphericalOrdering ordering) throws CycleException, ExplicitRedundancyException{
		if(orderings.contains(ordering)){
			throw new ExplicitRedundancyException("This user has already explicitly given this ordering");
		}
		// get corresponding internal nodes
		SphericalItem item1 = ordering.getItem1();
		SphericalItem item2 = ordering.getItem2();
		SphericalInternalNode iNode1 = null;
		SphericalInternalNode iNode2 = null;
		if(iNodes.containsKey(item1)){
			iNode1 = iNodes.get(item1);
		}
		if(iNodes.containsKey(item2)){
			iNode2 = iNodes.get(item2);
		}
		
		// check if both exist and the second has a path to the first
		if(iNode1 != null && iNode2 != null && canGetPath(iNode2, iNode1)){
			throw new CycleException("Cannot add "+ordering+" to Poset because causes a loop.");
		} else {
			orderings.add(ordering);
			items.add(item1);
			items.add(item2);
			if(iNode1==null){
				iNode1 = new SphericalInternalNode(item1);
			}
			if(iNode2==null){
				iNode2 = new SphericalInternalNode(item2);
			}
			iNode1.children.add(iNode2);
			iNode2.parents.add(iNode1);
			
			iNodes.put(item1, iNode1);
			iNodes.put(item2, iNode2);
		}
	}

	private boolean canGetPath(SphericalItem item1, SphericalItem item2) {
		if(iNodes.containsKey(item1) && iNodes.containsKey(item2)){
			return canGetPath(iNodes.get(item1), iNodes.get(item2));
		} else {
			return false;
		}
	}
	
	private boolean canGetPath(SphericalInternalNode node1, SphericalInternalNode node2) {
		if(node1.equals(node2)){
			return true;
		}
		//for(SphericalInternalNode child : node1.children){
		//	if(canGetPath(child,node2)){
		//		return true;
		//	}
		//}
		Stack<SphericalInternalNode> frontier = new Stack<SphericalInternalNode>();
		frontier.push(node1);
		return canGetPath(frontier, node2);
	}
	
	public boolean canGetPath(Stack<SphericalInternalNode> frontier, SphericalInternalNode node2){
		while(!frontier.isEmpty()){
			SphericalInternalNode top = frontier.pop();
			if(top.equals(node2)){
				return true;
			} else {
				for(SphericalInternalNode child : top.children){
					if(!frontier.contains(child)){
						frontier.push(child);
					}
				}
			}
		}
		return false;
	}
	
	public String toString(){
		StringBuffer str = new StringBuffer();
		for(SphericalOrdering ordering : orderings){
			str.append(ordering).append("\n");
		}
		return str.toString();
	}

	public TreeSet<SphericalItem> getItems() {
		return items;
	}

	public ArrayList<SphericalOrdering> getUnsatisfiedExplicitOrderings(SphericalPoset realPoset) {
		ArrayList<SphericalOrdering> unsatisfiedExplicitOrderings = new ArrayList<SphericalOrdering>();
		// For each explicit ordering, check if it can be found in the real ordering
		for(SphericalOrdering ordering : orderings){
			if(!realPoset.canGetPath(ordering.getItem1(), ordering.getItem2())){
				unsatisfiedExplicitOrderings.add(ordering);
			}
		}
		return unsatisfiedExplicitOrderings;
	}
}

class SphericalInternalNode implements Comparable<SphericalInternalNode>{
	public SphericalItem item;
	public ArrayList<SphericalInternalNode> children = new ArrayList<SphericalInternalNode>();
	public ArrayList<SphericalInternalNode> parents = new ArrayList<SphericalInternalNode>();

	public SphericalInternalNode(SphericalItem item){
		this.item = item;
	}

	@Override
	public int compareTo(SphericalInternalNode iNode) {
		return item.compareTo(iNode.item);
	}
	
	public boolean equals(Object iNode){
		if(iNode instanceof SphericalInternalNode){
			return compareTo((SphericalInternalNode)iNode) == 0;
		} else {
			return super.equals(iNode);
		}
	}

}
